home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-sip-rip-01.txt < prev    next >
Text File  |  1993-07-08  |  20KB  |  616 lines
  1.  
  2.  
  3. Internet Draft                                        G. Malkin/Xylogics
  4. Updates RFC 1058 and RFC 1288                           C. Huitema/INRIA
  5.                                                                June 1993
  6.  
  7.                                 SIP-RIP
  8.  
  9. Abstract
  10.  
  11.    This document specifies a routing protocol, based on the Routing
  12.    Information Protocol (RIP), as defined in [1,2], for the Simple
  13.    Internet Protocol (SIP), as defined in [3].
  14.  
  15.    A companion document will define the SNMP MIB objects for SIP-RIP
  16.    (TBD).
  17.  
  18.  
  19. Status of this Memo
  20.  
  21.    This document is an Internet Draft.  Internet Drafts are working
  22.    documents of the Internet Engineering Task Force (IETF), its Areas,
  23.    and its Working Groups.  Note that other groups may also distribute
  24.    working documents as Internet Drafts.
  25.  
  26.    Internet Drafts are draft documents valid for a maximum of six
  27.    months. Internet Drafts may be updated, replaced, or obsoleted by
  28.    other documents at any time.  It is not appropriate to use Internet
  29.    Drafts as reference material or to cite them other than as a "working
  30.    draft" or "work in progress."
  31.  
  32.    Please check the I-D abstract listing contained in each Internet
  33.    Draft directory to learn the current status of this or any other
  34.    Internet Draft.
  35.  
  36.    It is intended that this document will be submitted to the IESG for
  37.    consideration as a standards document.  Distribution of this document
  38.    is unlimited.
  39.  
  40.  
  41. Acknowledgements
  42.  
  43.    Thanks to those whose contributions to RIP-2 have been propogated
  44.    into SIP-RIP.  Special to Yakov Rekhter of IBM Research for
  45.    suggesting the "loop control" improvement, and to J.J. Garcia-Luna-
  46.    Aceves of UCSC for reviewing the text.
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54. Malkin, Huitema             Expires: 29Dec93                    [Page 1]
  55.  
  56. Internet Draft                  SIP-RIP                        June 1993
  57.  
  58.  
  59.                              Table of Contents
  60.  
  61.    1.  Justification . . . . . . . . . . . . . . . . . . . . . . . . .  2
  62.    2.  Overview  . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
  63.    3.  Protocol Design . . . . . . . . . . . . . . . . . . . . . . . .  3
  64.    3.1   Packet Format . . . . . . . . . . . . . . . . . . . . . . . .  3
  65.    3.2   Prefered Route Determination  . . . . . . . . . . . . . . . .  5
  66.    3.3   Loop Control  . . . . . . . . . . . . . . . . . . . . . . . .  6
  67.    3.4   Authentication  . . . . . . . . . . . . . . . . . . . . . . .  7
  68.    4.  Security Considerations . . . . . . . . . . . . . . . . . . . .  8
  69.    Appendicies . . . . . . . . . . . . . . . . . . . . . . . . . . . .  9
  70.    References  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
  71.    Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 11
  72.  
  73.  
  74. 1. Justification
  75.  
  76.    SIP is the Simple Internet Protocol.  It stands to reason that the
  77.    simplest, and best understood, routing protocol should be modified to
  78.    support it.  At the same time, SIP-RIP will make use of many of the
  79.    RIP-2 extensions.
  80.  
  81.  
  82. 2. Overview
  83.  
  84.    SIP-RIP is not a new version of IP RIP.  It is a new protocol which
  85.    will be run over its own UDP port.  Despite that, the changes are
  86.    only to the format of the routing entries within a routing packet,
  87.    the basic manipulation of routes and the routing table remains
  88.    unchanged.
  89.  
  90.    SIP-RIP makes use of most of the RIP-2 enhancements; only the route
  91.    tag field has been omitted.  The subnet mask has been replaced by a
  92.    single byte which specifies the number of bits in the subnet mask,
  93.    which therefore disallows the use of discontiguous subnet masks.  The
  94.    metric has been reduced to a single byte, but the maximum number of
  95.    hops permitted is now 32 instead of 16.  A new field, throughput
  96.    class, has been added to characterize the links which are used by a
  97.    route.  The most important change, however, is the increase in the
  98.    size of the address fields from 32 bits to 64 bits.
  99.  
  100.    SIP-RIP includes a loop control algorithm [5,6] which is not part of
  101.    RIP-2.  This algorithm makes SIP-RIP loop-free as it converges after
  102.    a topology change, but it requires that each routing entry carry a
  103.    First Hop field.  The new field brings the size of an entry from 24
  104.    to 32 bytes.
  105.  
  106.  
  107.  
  108.  
  109.  
  110. Malkin, Huitema             Expires: 29Dec93                    [Page 2]
  111.  
  112. Internet Draft                  SIP-RIP                        June 1993
  113.  
  114.  
  115. 3. Protocol Design
  116.  
  117.    SIP-RIP will be run on UDP port ???.  Periodic SIP-RIP responses will
  118.    be sent to the SIP "all routers on this link" multicast address,
  119.    7F02:0000:0000:0002.
  120.  
  121. 3.1 Packet Format
  122.  
  123.    IP RIP packets are limited to 25 routing entries which limits the
  124.    maximum packet size to 512 bytes (including UDP header).  This can
  125.    cause unnecessary overhead on LANs with larger MTUs when there are
  126.    more than 25 routes to be advertised.  Since routing updates are not
  127.    forwarded, there is no reason to artificially limit the maximum
  128.    packet size.  Therefore, the number of routing entries in any given
  129.    SIP RIP update shall be governed by the MTU of the link over which
  130.    the update is to be transmitted.  For example, on an Ethernet there
  131.    may be up to 45 entries in a single update (45 entries times 32 bytes
  132.    per entry plus 4 bytes of RIP header plus 8 bytes of UDP header plus
  133.    20 bytes of IP header equals 1484 bytes).
  134.  
  135.    A SIP-RIP packet has the following format.
  136.  
  137.     0                   1                   2                   3 3
  138.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  139.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  140.    |  Command (1)  |  Version (1)  |       Routing Domain (2)      |
  141.    +---------------+---------------+-------------------------------+
  142.    |    Type (1)   | Mask Length(1)|  TP Class (1) |   Metric (1)  |
  143.    +-------------------------------+-------------------------------+
  144.    |                        SIP Address (8)                        |
  145.    |                                                               |
  146.    +---------------------------------------------------------------+
  147.    |                         Next Hop (8)                          |
  148.    |                                                               |
  149.    +---------------------------------------------------------------+
  150.    |                         First Hop (8)                         |
  151.    |                                                               |
  152.    +---------------------------------------------------------------+
  153.  
  154.    All fields are coded in SIP network byte order (big-endian).
  155.  
  156.    Command:
  157.  
  158.       1 - request
  159.       2 - response
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166. Malkin, Huitema             Expires: 29Dec93                    [Page 3]
  167.  
  168. Internet Draft                  SIP-RIP                        June 1993
  169.  
  170.  
  171.    Version:
  172.  
  173.       1 - SIP-RIP version 1
  174.  
  175.    Routing Domain:
  176.  
  177.       The Routing Domain (RD) number is the number of the routing
  178.       process to which this update belongs. This field is used to
  179.       associate the routing update to a specific routing process on the
  180.       receiving router. The RD is needed to allow multiple, independent
  181.       RIP "clouds" to co-exist on the same physical wire.  This gives
  182.       administrators the ability to run multiple, possibly parallel,
  183.       instances of RIP in order to implement simple policy.  This means
  184.       that a router operating within one routing domain, or a set of
  185.       routing domains, should ignore RIP packets which belong to another
  186.       routing domain.  RD 0 is the default routing domain.
  187.  
  188.    Type:
  189.  
  190.       1 - Packet Authentication (see section 3.3)
  191.       2 - SIP Route
  192.  
  193.    Mask Length:
  194.  
  195.       The number of one bits in the address/subnet mask, moving left to
  196.       right.  The mask, when applied to the SIP address, yields the
  197.       non-host portion of the address.  Use of a mask length, rather
  198.       than a complete mask, allows the SIP route entries to be smaller.
  199.       The drawback, is that discontiguous masks cannot be specified.
  200.  
  201.    TP Class:
  202.  
  203.       The Throughput Class allows information about the bandwidth of the
  204.       route to be propogated between routers.  The throughput will be
  205.       encoded with the following formula.
  206.  
  207.          INT(10 * log10(datarate_in_Kbps))
  208.  
  209.       There will be no negative Throughput Classes, so datarates under
  210.       1Kbps will have a Throughput Class of 0.  The following table
  211.       shows the Throughput Classes for a few common datarates.
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222. Malkin, Huitema             Expires: 29Dec93                    [Page 4]
  223.  
  224. Internet Draft                  SIP-RIP                        June 1993
  225.  
  226.  
  227.          Datarate   TP Class        Datarate   TP Class
  228.          ___________________        ___________________
  229.          1200bps     0              4Mbps      36
  230.          9600bps     9              10Mbps     40
  231.          19.2Kbps   12              16Mbps     42
  232.          56Kbps     17              45Mbps     46
  233.          115.2Kbps  20              100Mbps    50
  234.          1.544Mbps  31              1Gbps      60
  235.  
  236.       Of course, the maximum datarate that can be encoded in one byte is
  237.       only 3,162,277,000,000,000,000Tbps.
  238.  
  239.    Metric:
  240.  
  241.       The number of hops to the destination.  Infinity is 32.
  242.  
  243.    SIP Address:
  244.  
  245.       The SIP address of this routes destination.
  246.  
  247.    Next Hop:
  248.  
  249.       The immediate next hop SIP address to which packets to the
  250.       destination specified by this route entry should be forwarded.
  251.       Specifying a value of 0 in this field indicates that routing
  252.       should be via the originator of the packet.  An address specified
  253.       as a next hop must, per force, be directly reachable on the
  254.       logical subnet over which the advertisement is made.
  255.  
  256.       The Next Hop field has two purposes.  The first purpose is to
  257.       eliminate packets being routed through extra hops in the system.
  258.       It is particularly useful when SIP-RIP is not being run on all of
  259.       the routers on a network, as exampled in Appendix A.  The second
  260.       purpose is to enable the efficient creation of "reverse trees" for
  261.       the routing of SIP multicast packets, as described in Appendix B.
  262.  
  263.    First Hop:
  264.  
  265.       The various routing entries determine a path between the local
  266.       router and the destination.  The First Hop field contains the SIP
  267.       address of the last router on this route before reaching the
  268.       destination.  This information is used to prevent the formation of
  269.       loops during the distributed computation of routes.
  270.  
  271. 3.2 Prefered Route Determination
  272.  
  273.    The prefered route is determined by taking into account both the
  274.    Throughput Class and the Metric according to the following rules.
  275.  
  276.  
  277.  
  278.  
  279. Malkin, Huitema             Expires: 29Dec93                    [Page 5]
  280.  
  281. Internet Draft                  SIP-RIP                        June 1993
  282.  
  283.  
  284.    1- When a routing update is received, the Metric is incremented by 1
  285.       and the Throughput Class is set to the minimum of:
  286.  
  287.       a) the received value decremented by 1, or zero if the received
  288.          value was zero;
  289.  
  290.       b) the Throughput Class of the subnet over which the update was
  291.          received.
  292.  
  293.       The effect of this rule is to diminish the throughput available
  294.       from remote links.  Only 80% of the link capacity appears
  295.       available after one relay.
  296.  
  297.    2- If the Metric has reached infinity, the route shall not be used.
  298.  
  299.    3- When two routes have different Throughput Classes, the route with
  300.       the larger Throughput Class value is considered to be the shorter,
  301.       prefered route.
  302.  
  303.    4- When two routes have equal Throughput Classes, the route with the
  304.       lesser Metric is the shorter, prefered route.
  305.  
  306. 3.3 Loop Control
  307.  
  308.    The First Hop field is initialized to a null value by the router that
  309.    initiates the route.  If a router receive a RIP message where the
  310.    First Hop field is null, it fills it with "its own address";
  311.    otherwise, the field will be propagated unchanged.  It is important,
  312.    for the loop detection to work, that the router picks exactly one of
  313.    its IP addresses, and always use this same address, to fill the First
  314.    Hop field.  It is also essential that the router propagates one route
  315.    that leads exactly to this IP address.
  316.  
  317.    The absence of a loop in a given route can be checked for by using
  318.    the algorithm presented in [5] and [6], which uses the First Hop
  319.    field.  For example, suppose that a host, L, wants to propagate a
  320.    route, R, to its neighbor, N.  Let H be the address of the first hop
  321.    for route R.  The loop detection algorithm can be executed by the
  322.    following pseudo-code.
  323.  
  324.       while (H != L) {
  325.          if (H == N)
  326.              return (LOOP_DETECTED);
  327.          Find R, the route towards H.
  328.          Let H be the first hop of the route R.
  329.       }
  330.       return (ROUTE_IS_SANE);
  331.  
  332.  
  333.  
  334.  
  335. Malkin, Huitema             Expires: 29Dec93                    [Page 6]
  336.  
  337. Internet Draft                  SIP-RIP                        June 1993
  338.  
  339.  
  340.    If a loop is detected, the metric of the route should be set to
  341.    infinity.
  342.  
  343.    There is a problem with this algorithm in the case of broadcast
  344.    networks where the SIP-RIP routes will be multicast to several
  345.    neighbors at the same time.  One simple resolution is to check the
  346.    route information received from broadcast networks, setting N to the
  347.    address of the local router and L to the address of the router that
  348.    sent the SIP-RIP message.
  349.  
  350.    One current practice within autonomous systems is to aggregate
  351.    routes; that is, propagating only one route with a prefix of "01101"
  352.    after receiving two different routes with prefixes of "011010" and
  353.    "011011".  This form of aggregation is incompatible with the loop
  354.    control algorithm, as the two aggregated routes have different First
  355.    Hops.  One way to maintain the loop control property of the algorithm
  356.    and also allow aggregation is to organize the autonomous systems as a
  357.    collection of areas, and to only authorize aggregations of routes
  358.    "coming out of the same area".
  359.  
  360. 3.4 Authentication
  361.  
  362.    The authentication mechanism is similar to that used in RIP-2.  If
  363.    the Type field of the first (and ONLY the first) entry in the packet
  364.    is type 1, then the remainder of the 20 byte entry is interpreted as
  365.    a packet authentication.  This means that there can be, at most, 24
  366.    RIP entries in the remainder of the packet.  If authentication is not
  367.    in use, then no entries in the packet should have an Type field value
  368.    of 1.
  369.  
  370.    The beginning of a packet with an authentication entry has the
  371.    following format.
  372.  
  373.     0                   1                   2                   3 3
  374.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  375.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  376.    |  Command (1)  |  Version (1)  |       Routing Domain (2)      |
  377.    +---------------+---------------+-------------------------------+
  378.    |   Type = 1    |  Authtype (1) |          reserved (2)         |
  379.    +-------------------------------+-------------------------------+
  380.    ~                       Authentication (16)                     ~
  381.    +---------------------------------------------------------------+
  382.  
  383.    Currently, the only Authentication Type is simple password and it is
  384.    type 2.  The Authentication field contains the plain text password.
  385.    If the password is under 16 bytes, it must be left-justified and
  386.    padded to the right with nulls (0x00).  A password is not null
  387.    terminated; it is 16 bytes long.
  388.  
  389.  
  390.  
  391. Malkin, Huitema             Expires: 29Dec93                    [Page 7]
  392.  
  393. Internet Draft                  SIP-RIP                        June 1993
  394.  
  395.  
  396. 4. Security Considerations
  397.  
  398.    SIP-RIP uses the same authentication mechanism as RIP-2.  The
  399.    authentication types are described in section 3.4
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447. Malkin, Huitema             Expires: 29Dec93                    [Page 8]
  448.  
  449. Internet Draft                  SIP-RIP                        June 1993
  450.  
  451.  
  452. Appendix A
  453.  
  454.               Use of SIP-RIP Next Hop to eliminate extra hops
  455.  
  456.       -----   -----   -----           -----   -----   -----
  457.       |IR1|   |IR2|   |IR3|           |XR1|   |XR2|   |XR3|
  458.       --+--   --+--   --+--           --+--   --+--   --+--
  459.         |       |       |               |       |       |
  460.       --+-------+-------+---------------+-------+-------+--
  461.         ^------------SIP-RIP------------^
  462.  
  463.    Assume that IR1, IR2, and IR3 are all "internal" routers which are
  464.    under one administration (e.g. a campus) which has elected to use SIP
  465.    RIP as its IGP.  XR1, XR2, and XR3, on the other hand, are under
  466.    separate administration (e.g. a regional network, of which the campus
  467.    is a member) and are using some other routing protocol (e.g. OSPF).
  468.    XR1, XR2, and XR3 exchange routing information among themselves such
  469.    that they know that the best routes to networks N1 and N2 are via
  470.    XR1, to N3, N4, and N5 are via XR2, and to N6 and N7 are via XR3.  By
  471.    setting the Next Hop field correctly (to XR2 for N3/N4/N5, to XR3 for
  472.    N6/N7), only XR1 need exchange SIP-RIP routes with IR1/IR2/IR3 for
  473.    routing to occur without additional hops through XR1.  Without the
  474.    Next Hop it would be necessary for XR2 and XR3 to also participate in
  475.    the SIP-RIP protocol to eliminate extra hops.
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503. Malkin, Huitema             Expires: 29Dec93                    [Page 9]
  504.  
  505. Internet Draft                  SIP-RIP                        June 1993
  506.  
  507.  
  508. Appendix B
  509.  
  510.                Use of SIP-RIP Next Hop for multicast routing
  511.  
  512.    Multicast routing is based on "reverse routes".  A multicast packet
  513.    from originator "O" received from subnet "S1" should only be
  514.    propagated on subnet "S2" if:
  515.  
  516.    1- The scope of the multicast address authorizes this relaying [3],
  517.  
  518.    2- The information obtained through SGMP [4] mentions that the
  519.       multicast address is "of interest" on subnet "S2", and
  520.  
  521.    3- A packet bound for the address "O" would have been routed through
  522.       subnet "S1".
  523.  
  524.    The route calculated by SIP-RIP can be used to implement the third
  525.    condition.  However, this condition is not sufficient to prevent
  526.    duplicate delivery when several routers are present on subnet "S2";
  527.    one must also analyze the "next hop" information received from these
  528.    routers.
  529.  
  530.    1- If the local router would not advertise on "S2" a null next hop
  531.       for the route leading to "O" through "S2", it should not propagate
  532.       the multicast packet.
  533.  
  534.    2- If several routers advertise a null next hop for the route leading
  535.       to "O" on "S2", only the router with the lesser SIP address shall
  536.       propagate the multicast packet.
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559. Malkin, Huitema             Expires: 29Dec93                   [Page 10]
  560.  
  561. Internet Draft                  SIP-RIP                        June 1993
  562.  
  563.  
  564. References
  565.  
  566.    [1] Hedrick, C., "Routing Information Protocol", Request For Comments
  567.        1058, Rutgers University, June 1988.
  568.  
  569.    [2] Malkin, G., "RIP Version 2 - Carrying Additional Information",
  570.        Request For Comments 1388, Xylogics, Inc., January, 1993.
  571.  
  572.    [3] Deering, S., "Simple Internet Protocol (SIP) Specification",
  573.        draft-deering-sip-00.txt, Xerox PARC, November 1992.
  574.  
  575.    [4] Davin, J., J.D. Case, M. Fedor, M.L. Schoffstall, "Simple Gateway
  576.        Monitoring Protocol", Request For Comments 1028, November 1987.
  577.  
  578.    [5] Cheng, C., R. Riley, S. Kumar, J.J. Garcia-Luna-Aceves, "A Loop-
  579.        Free Extended Bellman-Ford Routing Protocol Without Bouncing
  580.        Effect", ACM Sigcomm'89 symposium, September 1989.
  581.  
  582.    [6] Rajagopalan, B., M. Faiman, "A New Responsive Distributed
  583.        Shortest-Path Routing Algorithm", ACM Sigcomm'89 symposium,
  584.        September 1989.
  585.  
  586. Authors' Addresses
  587.  
  588.    Gary Scott Malkin
  589.    Xylogics, Inc.
  590.    53 Third Avenue
  591.    Burlington, MA 01803
  592.  
  593.    Phone: (617) 272-8140
  594.    EMail: gmalkin@Xylogics.COM
  595.  
  596.  
  597.    Christian Huitema
  598.    INRIA
  599.    2004 Route des Lucioles, BP 93
  600.    06902 Sophia-Antipolis, France
  601.  
  602.    Phone: +33 93 65 77 15
  603.    EMail: Christian.Huitema@sophia.inria.fr
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615. Malkin, Huitema             Expires: 29Dec93                   [Page 11]
  616.